package org.usmile.algorithms.leetcode.middle;

/**
 * 767. 重构字符串
 *
 * 给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。
 * 返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。
 *
 * 示例 1:
 * 输入: s = "aab"
 * 输出: "aba"
 *
 * 示例 2:
 * 输入: s = "aaab"
 * 输出: ""
 *
 * 提示:
 * 1 <= s.length <= 500
 * s 只包含小写字母
 */
public class _0767 {
}

class _0767_Solution {
    public String reorganizeString(String s) {
        // 1. 统计每个字符出现的次数
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[] count = new int[26];
        for (char c : chars) {
            int index = c - 'a';
            count[index]++;
            if (count[index] > (n + 1) / 2) {
                return "";
            }
        }

        // 2. 拿到出现次数最多的字符
        int maxCountIndex = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] > count[maxCountIndex]) {
                maxCountIndex = i;
            }
        }

        // 3. 先将出现次数最多的字符放在偶数索引上
        char[] res = new char[n];
        int idx = 0;
        while (count[maxCountIndex] > 0) {
            res[idx] = (char) (maxCountIndex + 'a');
            idx += 2;
            count[maxCountIndex]--;
        }

        // 4. 将其他的字符放到其他的位置
        for (int i = 0; i < 26; i++) {
            while (count[i] > 0) {
                if (idx >= n) {
                    idx = 1;
                }
                res[idx] = (char) (i + 'a');
                idx += 2;
                count[i]--;
            }
        }

        return new String(res);
    }
}